import java.util.Arrays;

class Solution {
    public int[] productExceptSelf2(int[] nums) {
        // 暴力枚举
        int len = nums.length;
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            // 计算出i位置之外，其余元素的乘积
            int n = 1; // 这里一定不能是0
            for (int j = 0; j < len; j++) {
                if (j == i) { // 排除自身
                    continue;
                }
                if (nums[j] == 0) { // 存在0的话，那么最终的结果一定是0
                    n = 0;
                    break;
                }
                n *= nums[j];
            }
            ans[i] = n;
        }
        return ans;
    }

    public int[] productExceptSelf1(int[] nums) {
        // 暴力枚举
        int len = nums.length;
        int[] ans = new int[len];
        int n = 1; // 这里一定不能是0
        // 先将全部的值计算出来
        for (int i = 0; i < len; i++) {
            n *= nums[i];
            if (nums[i] == 0) {
                n = 0;
                break;
            }
        }
        Arrays.fill(ans, 1); // 一定要填充为1，之后才能使用
        for (int i = 0; i < len; i++) {
            // 计算出i位置之外，其余元素的乘积
            if (n == 0) { // 说明数组中存在0元素
                // 判断当前元素是不是0
                if (nums[i] == 0) {
                    // 计算除其之外的乘积
                    for (int j = 0; j < len; j++) {
                        if (j == i) { // 排除自身
                            continue;
                        }
                        ans[i] *= nums[j]; // 先得将ans中的元素全部初始化为1
                    }
                } else {
                    ans[i] = 0;
                }
            } else { // 直接除以当前位置即可
                ans[i] = n / nums[i];
            }
        }
        return ans;
    }

    public int[] productExceptSelf(int[] nums) {
        // 前缀和思想优化
        int n = nums.length;
        int[] ans = new int[n];
        int[] left_nums = new int[n+1];
        int[] right_nums = new int[n+1];
        // 初始化数组
        // Arrays.fill(left_nums, 1);
        // Arrays.fill(right_nums, 1);
        left_nums[0] = 1;
        right_nums[n-1] = 1;
        // 填充数组(0和n-1对应的数组得特殊处理)
        for (int i = 1; i <= n; i++) {
            left_nums[i] = left_nums[i-1] * nums[i-1];
        }
        for (int i = n-2; i >= 0; i--) {
            right_nums[i] = right_nums[i+1] * nums[i+1];
        }
        // 开始填充ans数组
        for (int i = 0; i < n; i++) {
            ans[i] = left_nums[i] * right_nums[i];
        }
        return ans;
    }
}